/*
 * @FilePath: /data-and-structure-lv/02/merge/merge-sort2.c
 * @Brief: 
 * @Version: 1.0
 * @Date: 2021-12-12 10:08:52
 * @Author: zsk
 * @Copyright: open source
 * @LastEditors: zsk
 * @LastEditTime: 2021-12-12 10:20:29
 */
#include <stdio.h>

#define MAX ((unsigned int)-1 >> 1)

typedef int ElementType;

void merge(ElementType *a, int p, int q, int r)
{
    int n1 = q - p + 1;
    int n2 = r - q;
    ElementType left[n1], right[n2];
    int i = 0, j = 0;
    for (i = 0; i < n1; i++)
    {
        left[i] = a[p + i];
    }
    for (j = 0; j < n2; j++)
    {
        right[j] = a[q + j + 1];
    }
    i = 0;
    j = 0;
    for (int k = p; k <= r; k++)
    {
        if ((i < n1 && left[i] <= right[j]) || j == n2)
        {
            /* code */
            a[k] = left[i];
            i++;
        }
        else
        {
            a[k] = right[j];
            j++;
        }
    }
}

void merge_sort(ElementType *a, int p, int r)
{
    if (p < r)
    {
        /* code */
        int q = (p + r) / 2;
        merge_sort(a, p, q);
        merge_sort(a, q + 1, r);
        merge(a, p, q, r);
    }
}

void print_array(ElementType *a, int length)
{
    for (int i = 0; i < length; i++)
    {
        /* code */
        printf("%d ", a[i]);
    }
    printf("\n");
}

void main()
{
    ElementType a[] = {2, 4, 5, 7, 1, 2, 3, 6};
    int length = 8;
    merge(a, 0, (length - 1) / 2, length - 1);
    print_array(a, length);

    length = 8;
    ElementType b[] = {5, 2, 4, 7, 1, 3, 2, 6};
    merge_sort(b, 0, length - 1);
    print_array(b, length);
}